package com.example.algorithm.huawei_rongyao_29;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

// n个数里出现次数大于等于n/2的数
// 难度：简单

/**
 输入n个整数，输出出现次数大于等于数组长度一半的数。
 输入描述:
 每个测试输入包含 n个空格分割的n个整数，n不超过100，其中有一个整数出现次数大于等于n/2。
 输出描述:
 输出出现次数大于等于n/2的数。

 3 9 3 2 5 6 7 3 2 3 3 3
 3
 * */
public class Q13_MajorityElement {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        while (scanner.hasNextLine()) {
            String[] input = scanner.nextLine().split(" ");
            int[] nums = new int[input.length];
            for (int i = 0; i < input.length; i++) {
                nums[i] = Integer.parseInt(input[i]);
            }
            System.out.println(findMajorityElement(nums));
        }

        scanner.close();
    }

    public static int findMajorityElement(int[] nums) {
        // 用来装次数的
        Map<Integer, Integer> countMap = new HashMap<>();

        for (int num : nums) {
            // 键是元素本身。值是元素出现的次数。
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }

        int threshold = nums.length / 2;
        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            if (entry.getValue() >= threshold) {
                return entry.getKey();
            }
        }

        return -1; // No majority element found
    }
}

